SherbyNet - /page/wikibook/entry.mu

<!DOCTYPE html>

<title>Standard array</title>

</head>

<span id="openzim-page-title" class="mw-page-title-main"><span class="mw-page-title-main">Standard array</span></span>

</h1>

</header>

<p>In <a href="Coding_theory" title="Coding theory">coding theory</a>, a <b>standard array</b> (or Slepian array) is a <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q^{n-k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q^{n-k}}</annotation>

</semantics>

</math></span><img src="./4cf44f5c6a300293184c889ce4242976b00552c7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.433ex; height:3.009ex;" alt="{\displaystyle q^{n-k}}" loading="lazy"></span> by <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q^{k}}</annotation>

</semantics>

</math></span><img src="./fc9b1525f5a653e19f9fd37fd2701a768e171632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.168ex; height:3.009ex;" alt="{\displaystyle q^{k}}" loading="lazy"></span> array that lists all elements of a particular <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \mathbb {F} _{q}^{n}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \mathbb {F} _{q}^{n}}</annotation>

</semantics>

</math></span><img src="./0a630603c6f2f8f58f5d1fb9ef1b9ad194e258a2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.171ex; width:2.639ex; height:3.176ex;" alt="{\displaystyle \mathbb {F} _{q}^{n}}" loading="lazy"></span> <a href="Vector_space" title="Vector space">vector space</a>. Standard arrays are used to <a href="Decoding_methods" title="Decoding methods">decode</a> <a href="Linear_code" title="Linear code">linear codes</a>; i.e. to find the corresponding <a href="Code_word_(communication)" title="Code word (communication)">codeword</a> for any received vector.

</p>

<div class="mw-heading mw-heading2"><h2 id="Definition">Definition</h2></div>

<p>A standard array for an [<i>n</i>,<i>k</i>]-code is a <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q^{n-k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q^{n-k}}</annotation>

</semantics>

</math></span><img src="./4cf44f5c6a300293184c889ce4242976b00552c7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.433ex; height:3.009ex;" alt="{\displaystyle q^{n-k}}" loading="lazy"></span> by <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q^{k}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q^{k}}</annotation>

</semantics>

</math></span><img src="./fc9b1525f5a653e19f9fd37fd2701a768e171632.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.168ex; height:3.009ex;" alt="{\displaystyle q^{k}}" loading="lazy"></span> array where:

</p>

<ol><li>The first row lists all <a href="Code_word_(communication)" title="Code word (communication)">codewords</a> (with the <u>0</u> codeword on the extreme left)</li>

<li>Each row is a <a href="Coset" title="Coset">coset</a> with the <a href="Coset_leader" title="Coset leader">coset leader</a> in the first column</li>

<li>The entry in the i-th row and j-th column is the sum of the i-th coset leader and the j-th codeword.</li></ol>

<p>For example, the [<i>5</i>,<i>2</i>]-code <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{3}}</annotation>

</semantics>

</math></span><img src="./66e9abeb5057b7afbf88e3169101849354f13c65.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.716ex; height:2.509ex;" alt="{\displaystyle C_{3}}" loading="lazy"></span> = {<u>0</u>, 01101, 10110, 11011} has a standard array as follows:

</p>

</td>

<td>01101

</td>

<td>10110

</td>

<td>11011

</td></tr>

<tr>

<td>10000

</td>

<td>11101

</td>

<td>00110

</td>

<td>01011

</td></tr>

<tr>

<td>01000

</td>

<td>00101

</td>

<td>11110

</td>

<td>10011

</td></tr>

<tr>

<td>00100

</td>

<td>01001

</td>

<td>10010

</td>

<td>11111

</td></tr>

<tr>

<td>00010

</td>

<td>01111

</td>

<td>10100

</td>

<td>11001

</td></tr>

<tr>

<td>00001

</td>

<td>01100

</td>

<td>10111

</td>

<td>11010

</td></tr>

<tr>

<td>11000

</td>

<td>10101

</td>

<td>01110

</td>

<td>00011

</td></tr>

<tr>

<td>10001

</td>

<td>11100

</td>

<td>00111

</td>

<td>01010

</td></tr></tbody></table>

<p>The above is only one possibility for the standard array; had 00011 been chosen as the first <a href="Coset_leader" title="Coset leader">coset leader</a> of weight two, another standard array representing the code would have been constructed.

</p><p>The first row contains the <u>0</u> vector and the codewords of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C_{3}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C_{3}}</annotation>

</semantics>

</math></span><img src="./66e9abeb5057b7afbf88e3169101849354f13c65.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.716ex; height:2.509ex;" alt="{\displaystyle C_{3}}" loading="lazy"></span> (<u>0</u> itself being a codeword). Also, the leftmost column contains the vectors of <a href="Hamming_weight" title="Hamming weight">minimum weight</a> enumerating vectors of weight 1 first and then using vectors of weight 2. Also each possible vector in the vector space appears exactly once.

</p>

<div class="mw-heading mw-heading2"><h2 id="Constructing_a_standard_array">Constructing a standard array</h2></div>

<p>Because each possible vector can appear only once in a standard array some care must be taken during construction. A standard array can be created as follows:

</p>

<ol><li>List the codewords of <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math></span><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"></span>, starting with <u>0</u>, as the first row</li>

<li>Choose any vector of minimum weight not already in the array. Write this as the first entry of the next row. This vector is denoted the '<b>coset leader'</b>.</li>

<li>Fill out the row by adding the coset leader to the codeword at the top of each column. The sum of the i-th coset leader and the j-th codeword becomes the entry in row i, column j.</li>

<li>Repeat steps 2 and 3 until all rows/cosets are listed and each vector appears exactly once.</li></ol>

<p>Adding vectors is done mod q. For example, binary codes are added mod 2 (which equivalent to bit-wise XOR addition). For example, in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Z_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Z_{2}}</annotation>

</semantics>

</math></span><img src="./c98d433ae289ecb2b88f895b407538b0e4183b28.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.642ex; height:2.509ex;" alt="{\displaystyle Z_{2}}" loading="lazy"></span>, 11000 + 11011 = 00011.

</p><p>That selecting different coset leaders will create a slightly different but equivalent standard array, and will not affect results when decoding.

</p>

<div class="mw-heading mw-heading3"><h3 id="Construction_example">Construction example</h3></div>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math></span><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"></span> be the <a href="Binary_code" title="Binary code">binary</a> [4,2]-code. i.e. C = {0000, 1011, 0101, 1110}. To construct the standard array, we first list the codewords in a row.

</p>

<td>0000

</td>

<td>1011

</td>

<td>0101

</td>

<td>1110

</td></tr></tbody></table>

<p>We then select a vector of minimum weight (in this case, weight 1) that has not been used. This vector becomes the coset leader for the second row.

</p>

<td>0000

</td>

<td>1011

</td>

<td>0101

</td>

<td>1110

</td></tr>

<tr>

<td>1000

</td>

<td>

</td>

<td>

</td>

<td>

</td></tr></tbody></table>

<p>Following step 3, we complete the row by adding the coset leader to each codeword.

</p>

<td>0000

</td>

<td>1011

</td>

<td>0101

</td>

<td>1110

</td></tr>

<tr>

<td>1000

</td>

<td>0011

</td>

<td>1101

</td>

<td>0110

</td></tr></tbody></table>

<p>We then repeat steps 2 and 3 until we have completed all rows. We stop when we have reached <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle q^{n-k}=2^{4-2}=2^{2}=4}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle q^{n-k}=2^{4-2}=2^{2}=4}</annotation>

</semantics>

</math></span><img src="./2faa5bb4611427dda8df347a354e67ed108904ec.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:21.425ex; height:3.009ex;" alt="{\displaystyle q^{n-k}=2^{4-2}=2^{2}=4}" loading="lazy"></span> rows.

</p>

<td>0000

</td>

<td>1011

</td>

<td>0101

</td>

<td>1110

</td></tr>

<tr>

<td>1000

</td>

<td>0011

</td>

<td>1101

</td>

<td>0110

</td></tr>

<tr>

<td>0100

</td>

<td>1111

</td>

<td>0001

</td>

<td>1010

</td></tr>

<tr>

<td>0010

</td>

<td>1001

</td>

<td>0111

</td>

<td>1100

</td></tr></tbody></table>

<p>In this example we could not have chosen the vector 0001 as the coset leader of the final row, even though it meets the criteria of having minimal weight (1), because the vector was already present in the array. We could, however, have chosen it as the first coset leader and constructed a different standard array.

</p>

<div class="mw-heading mw-heading2"><h2 id="Decoding_via_standard_array">Decoding via standard array</h2></div>

<p>To decode a vector using a standard array, subtract the error vector - or coset leader - from the vector received. The result will be one of the codewords in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle C}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle C}</annotation>

</semantics>

</math></span><img src="./4fc55753007cd3c18576f7933f6f089196732029.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.766ex; height:2.176ex;" alt="{\displaystyle C}" loading="lazy"></span>. For example, say we are using the code C = {0000, 1011, 0101, 1110}, and have constructed the corresponding standard array, as shown from the example above. If we receive the vector 0110 as a message, we find that vector in the standard array. We then subtract the vector's coset leader, namely 1000, to get the result 1110. We have received the codeword 1110.

</p><p>Decoding via a standard array is a form of <a href="Nearest_neighbour_decoding" class="mw-redirect" title="Nearest neighbour decoding">nearest neighbour decoding</a>. In practice, decoding via a standard array requires large amounts of storage - a code with 32 codewords requires a standard array with <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 2^{32}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 2^{32}}</annotation>

</semantics>

</math></span><img src="./a8c222ea8e5f187a2bb499395b6f4a6f38b43633.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.039ex; height:2.676ex;" alt="{\displaystyle 2^{32}}" loading="lazy"></span> entries. Other forms of decoding, such as <a href="Syndrome_decoding" class="mw-redirect" title="Syndrome decoding">syndrome decoding</a>, are more efficient.

</p><p>Decoding via standard array does not guarantee that all vectors are decoded correctly. If we receive the vector 1010, using the standard array above would decode the message as 1110, a codeword distance 1 away. However, 1010 is also distance 1 away from the codeword 1011. In such a case some implementations might ask for the message to be resent, or the ambiguous bit may be marked as an erasure and a following <a href="Concatenated_error_correction_code" title="Concatenated error correction code">outer code</a> may correct it. This ambiguity is another reason that different decoding methods are sometimes used.

</p>

<ul><li><a href="Linear_code" title="Linear code">Linear code</a></li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFHill1986" class="citation book cs1">Hill, Raymond (1986). <span class="id-lock-registration" title="Free registration required"><a rel="nofollow" class="external text" href="https://archive.org/details/firstcourseincod0000hill"><i>A First Course in Coding Theory</i></a></span>. Oxford Applied Mathematics and Computing Science series. <a href="Oxford_University_Press" title="Oxford University Press">Oxford University Press</a>. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-0-19-853803-5</bdi>.</cite></li></ul></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2023-12-26" href="https://en.wikipedia.org/wiki/?title=Standard_array&oldid=1191967860">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>